package backtrackAlgorithm;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

//n皇后问题
public class LeetCode_51 {
    private List<List<String>> result ;

    @Test
    public void test(){
//        List<List<String>> lists = solveNQueens(5);
//        System.out.println(lists.size());
//        for (List<String> list : lists) {
//            for (String s : list) {
//                System.out.print(s+" ");
//            }
//            System.out.println();
//        }

        int n=5;
        int limit = (1 << n) - 1;
        int[] arr = new int[n+1];
        result = new ArrayList<List<String>>();
        solution_2(limit, 0, 0, 0, arr, n,1);
        for (List<String> list : result) {
            for (String s : list) {
                System.out.print(s+" ");
            }
            System.out.println();
        }


    }

    public List<List<String>> solveNQueens(int n) {
        result = new ArrayList<List<String>>();
        int[] arr = new int[n+1];
//        solution_1(1,n,arr);
        int limit = (1 << n) - 1;
        solution_2(limit, 0, 0, 0, arr, n,1);
        return result ;


    }

    /**
     * 递归解法1
     * @param i 第i行
     * @param n n皇后
     * @param arr 存放每行皇后的位置
     * @return
     */
    private void solution_1(int i, int n, int[] arr) {
        //1. 递归截止条件
        if (i>n){
            List<String> list = save(arr, n);
            result.add(list);
            return;
        }
        for (int j = 1; j <= n ; j++) {
            if (check(arr,i,j)){
                arr[i] = j;
                solution_1(i+1,n,arr);
            }

        }

    }

    /**
     * 解法2--位运算
     * @param limit 限制（n个1）
     * @param colLimit 列限制
     * @param leftLimit 左边限制
     * @param rightLimit 右边限制
     * @return
     */
    private void solution_2(int limit,int colLimit,int leftLimit,int rightLimit,int arr[],int n,int k) {

        //1. 递归终止条件
        if (colLimit==limit){
//            return 1;
            List<String> list = save(arr, n);
            result.add(list);
            return;

        }
        //2. 定义pos和mostRightOne，pos表示当前列，mostRightOne表示最右侧的1的位置
        int pos=0,mostRightOne=0;
//        int res=0;
        pos=limit & (~(colLimit|leftLimit|rightLimit));
        //3. 循环遍历
        while(pos!=0){
            //3.1 找到最右侧的1的位置
            mostRightOne = pos & (~pos+1);
            arr[k]=findIndex_1(mostRightOne,n);
            pos-=mostRightOne;
            solution_2(limit,colLimit|mostRightOne
                    ,(leftLimit|mostRightOne)<<1,
                    (rightLimit|mostRightOne)>>>1,
                    arr,n,k+1);
        }
//        return res;
    }

    //保存结果
    private List<String> save(int[] arr, int n) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            String s = "";
            for (int j = 1; j <= n; j++) {
                if (arr[j] == i) {
                    s += "Q";
                } else {
                    s += ".";
                }
            }
            list.add(s);
        }
        return list;
    }

    //检查是否可以放置
    private boolean check(int[] arr, int i, int j) {
        for (int k = 1; k < i; k++) {
            if (arr[k] == j || Math.abs(k - i) == Math.abs(arr[k] - j)) {
                return false;
            }
        }
        return true;
    }

    //检查最右侧1的位置
    private int findIndex_1(int pos,int n){
        int i=0;
        while(pos!=0){
            if ((pos & 1) == 1){
                return n-i;
            }
            i++;
            pos>>=1;
        }
        return -1;
    }
}
